The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

1(q0(1(x1))) → 0(1(q1(x1)))
1(q0(0(x1))) → 0(0(q1(x1)))
1(q1(1(x1))) → 1(1(q1(x1)))
1(q1(0(x1))) → 1(0(q1(x1)))
0(q1(x1)) → q2(1(x1))
1(q2(x1)) → q2(1(x1))
0(q2(x1)) → 0(q0(x1))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1.
The certificate found is represented by the following graph.

Start state: 1123
Accept states: [1124, 1126]
Transitions:
1123→1124[1_1|0]
1123→1126[0_1|0]
1123→1123[q0_1|0, q1_1|0, q2_1|0]
1123→1129[1_1|1]
1123→1130[1_1|1]
1123→1131[q0_1|1]
1129→1126[q2_1|1]
1130→1124[q2_1|1]
1130→1129[q2_1|1]
1130→1130[q2_1|1]
1131→1126[0_1|1]

(2) BOUNDS(O(1), O(n^1))